package lcr;

import java.util.Arrays;

public class Test0097 {

    public static void main(String[] args) {
        new Solution0097_1().numDistinct("rabbbit","rabbit");
    }
}

class Solution0097_1 {
    public int numDistinct(String s, String t) {
        int length1 = s.length();
        int length2 = t.length();
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();

        int[] pre = new int[length1 + 1];
        int[] cur = new int[length1 + 1];

        Arrays.fill(pre,1);

        for (int i = 0; i < length2; i++) {
            char c1 = chars2[i];

            for (int j = 1; j <= length1; j++) {
                char c2=chars1[j-1];

                cur[j]=cur[j-1];
                if (c1==c2) cur[j]+=pre[j-1];
            }

            pre[0]=0;
            int[] temp = pre;
            pre=cur;
            cur=temp;


        }

        return pre[length1];
    }
}